/**
 * 动态规划
 */
// var trap = function (height) {
//   const n = height.length
//   if (n == 0) return 0

//   // leftMax表示下标i及其左边的位置中height的最大高度
//   const leftMax = new Array(n).fill(0)
//   leftMax[0] = height[0]
//   for (let i = 1; i < n; i++) {
//     leftMax[i] = Math.max(height[i], leftMax[i - 1])
//   }

//   // rightMax表示下标i及其右边的位置中height的最大高度
//   const rightMax = new Array(n).fill(0)
//   rightMax[n - 1] = height[n - 1]
//   for (let i = n - 2; i >= 0; --i) {
//     rightMax[i] = Math.max(height[i], rightMax[i + 1])
//   }

//   let ans = 0
//   for (let i = 0; i < n; ++i) {
//     ans += Math.min(leftMax[i], rightMax[i]) - height[i]
//   }
//   return ans
// }

/**
 * 双指针
 * @param {*} height
 * @returns
 */
var trap = function (height) {
  let ans = 0
  let left = 0, // 左指针
    right = height.length - 1 // 右指针
  let leftMax = 0, // 左边能接的雨水的最大值
    rightMax = 0 // 右边能接的雨水的最大值

  while (left < right) {
    leftMax = Math.max(leftMax, height[left]) // 更新左边能接的雨水的最大值
    rightMax = Math.max(rightMax, height[right]) // 更新右边能接的雨水的最大值
    if (height[left] < height[right]) {
      // 当前的左下标比右下标小
      ans += leftMax - height[left]
      ++left
    } else {
      ans += rightMax - height[right]
      --right
    }
  }
  return ans
}
